package com.sise.Tree;

/**
 * 二叉搜索树的增删查改
 *
 * 总结：
 *      通过这篇文章，你学会了如下几个技巧：
 *      二叉树算法设计的总路线：把当前节点要做的事做好，其他的交给递归框架，不用当前节点操心。
 *      如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。
 *      在二叉树框架之上，扩展出一套 BST 遍历框架：
 *  void BST(TreeNode root, int target) {
 *     if (root.val == target)
 *         // 找到目标，做点什么
 *     if (root.val < target)
 *         BST(root.right, target);
 *     if (root.val > target)
 *         BST(root.left, target);
 *  }
 *
 */
public class TreeCRUD {

    /**
     * 在 BST 中查找一个数是否存在
     */
    boolean isInBST(TreeNode root, int target) {
        if (root == null) return false;
        if (root.val == target)
            return true;
        if (root.val < target)
            return isInBST(root.right, target);
        if (root.val > target)
            return isInBST(root.left, target);
        // root 该做的事做完了，顺带把框架也完成了，妙

        // 前面已经覆盖了所有情况，故此最后返回 false
        return false;
    }

    /**
     *  BST 插入一个数字
     *  这里没有考虑平衡问题，
     */
    TreeNode insertIntoBST(TreeNode root, int val) {
        // 找到空位置插入新节点
        if (root == null) return new TreeNode(val);
        // if (root.val == val)
        //     BST 中一般不会插入已存在元素
        if (root.val < val)
            root.right = insertIntoBST(root.right, val);
        if (root.val > val)
            root.left = insertIntoBST(root.left, val);
        return root;
    }

    /**
     *  在 BST 中删除一个数
     *
     *  删除操作就完成了。注意一下，这个删除操作并不完美，因为我们一般不会通过 root.val = minNode.val 修改节点内部的值来交换节点，
     *  而是通过一系列略微复杂的链表操作交换 root 和 minNode 两个节点。因为具体应用中，val 域可能会很大，修改起来很耗时，而链表操作无非改一改指针，而不会去碰内部数据。
     *  但这里忽略这个细节，旨在突出 BST 基本操作的共性，以及借助框架逐层细化问题的思维方式。
     *
     */
    TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {

            // 情况1： 如果该节点是尾结点，那么它的左右节点都为空，直接返回 null
//            if (root.left == null && root.right == null){
//                return null;
//            }

            // 情况2： 如果该节点只有一个尾结点，那么有可能是 左节点或右节点，那么让它的孩子替换它的位置即可
            // 这两个 if 把情况 1 和 2 都正确处理了
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            // 处理情况 3： 它有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。
            TreeNode minNode = getMin(root.right);
            // 把 root 改成 minNode
            root.val = minNode.val;
            // 转而去删除 minNode，因为找到的 右子树的最小点，故此向右子树遍历。 到时候又回归了删除尾结点，故此返回 null，此时 root.right = null(返回值)
            // root.val = minNode.val 这里只是赋值，并没有改变原本的 子树结构连接
            root.right = deleteNode(root.right, minNode.val);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    TreeNode getMin(TreeNode node) {
        // BST 最左边的就是最小的
        while (node.left != null) node = node.left;
        return node;
    }


}
